# !usr/bin/python
# -*-coding: utf-8-*-
# FileName: 8Queen.py

MAXX = 6
MAXY = 6
count = 0


# 皇后是否放置  0 没有  1 有
node = [[0 for i in range(MAXX)] for i in range(MAXY)]

def check(x , y):
	global MAXX
	global MAXY
	global node

	for i in range(0, MAXX):
		for j in range(0, MAXY):
			if( node[i][j] == 1 ):
				if( x == i ):
					return False
				if( y == j ):
					return False
				if( abs(x-i) == abs(y-j) ):
					return False

	return True

def fun1(x, y):
	global MAXX
	global MAXY
	global count
	global node

	if( x < 0 or x > MAXX-1 ):
		return
	if( y < 0 or y > MAXY-1 ):
		return	
	
	if( check( x, y ) == False ):
		fun1( x+1, y )
		return

	if( y == MAXY-1 ):
		count += 1
		return

	node[x][y] = 1
	fun1( 0, y+1 )
	# 回溯
	node[x][y] = 0

	fun1( x+1, y )

def fun2(x , y):
	global MAXX
	global MAXY
	global count
	global node

	if( x < 0 or x > MAXX-1 ):
		return
	if( y < 0 or y > MAXY-1 ):
		return

	i = 0
	while( i < MAXX ):
		if( check(i,y) == True ):
			node[i][y] = 1
			fun2(0, y+1)
		
			if( y == MAXY-1 ):
				count += 1

			# 回溯
			node[i][y] = 0

		i += 1

count = 0
fun1(0,0)
print('fun1 :' + str(count))

count = 0
fun2(0,0)
print('fun2 :' + str(count))


